// const deepTree = (data, arr = []) => {
//   arr.push(data.value);

//   if (data.children && data.children.length > 0) {
//     data.children.forEach(child => {
//       deepTree(child, arr)
//     });
//   }

//   return arr
// }

// // 基于栈
const traverseTree = (tree, arr = []) => {
  let stack = [tree]
  while (stack.length) {
    let node = stack.shift()
    arr.push(node.value)
    if (node.children && node.children.length > 0) {
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.unshift(node.children[i])
      }
    }
  }
  return arr
}

const tree = {
  value: 'A',
  children: [
    {
      value: 'B',
      children: [
        {
          value: 'C',
          children: []
        },
        {
          value: 'D',
          children: []
        }
      ]
    },
    {
      value: 'E',
      children: [
        {
          value: 'F',
          children: [
            {
              value: 'G',
              children: []
            }
          ]
        }
      ]
    }
  ]
}
// console.log(deepTree(tree, []));
console.log(traverseTree(tree, []));

// 广度优先遍历
const bfs = (tree, rst = []) => {
  // 基于队列实现
  let queue = []
  queue.push(tree)
  while (queue.length) {
    let node = queue.shift() // 队头即数组第一个元素
    rst.push(node.value)
    if (node.children && node.children.length > 0) {
      node.children.forEach(child => {
        queue.push(child)
      })
    }
  }
  return rst
}
console.log(bfs(tree));